/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
// var invertTree = function (root) {

//     const tool = (root) => {
//         if (root === null) { return null }
//         const temp = root.left
//         root.left = root.right
//         root.right = temp
//         tool(root.left)
//         tool(root.right)
//     }
//     tool(root)
//     return root
// };

//迭代法

const tree = {
  val: 1,
  left: {
    val: 2,
    left: {
      val: 4,
      left: null,
      right: null,
    },
    right: {
      val: 5,
      left: null,
      right: null,
    },
  },
  right: {
    val: 3,
    left: {
      val: 6,
      left: null,
      right: null,
    },
    right: null,
  },
};

var inorderTraversal = function (root) {
  const targrt = [];
  const stack = [];
  while (root || stack.length) {
    while (root) {
      stack.push(root);
      root = root.left;
    }
    root = stack.pop();
    targrt.push(root.val);
    root = root.right;
  }
  return targrt;
};

console.log(inorderTraversal(tree));
